package codeRandomThoughts.Test84柱状图中最大的矩形;

//暴力,会超时
public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;

        for (int i = 0; i < heights.length; i++) {
            //找左边第一个比自己小的位置
            int leftIndex = -1;
            for (int j = i - 1; i >= 1 && j >= 0; j--) {
                if (heights[j] < heights[i]) {
                    leftIndex = j;
                    break;
                }
            }
            //找右边第一个比自己小的位置
            int rightIndex = heights.length;
            for (int j = i + 1; i < heights.length - 1 && j < heights.length; j++) {
                if (heights[j] < heights[i]) {
                    rightIndex = j;
                    break;
                }
            }

            maxArea = Math.max((rightIndex - leftIndex - 1) * heights[i], maxArea);
        }
        return maxArea;
    }
}
